package sort.heap;

import org.junit.Test;

import java.util.Arrays;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-04-30 17:41
 * 时间复杂度: O(n*logn)
 * 堆排序
 * 整个过程就分为两个步骤：
 * 1)构建大根堆并输出堆顶元素
 * 2)调整剩余元素为大根堆,继续输出堆顶，重复该过程直到所有元素输出完毕
 * 时间复杂度分析: (这块不太理解的就这样记着就行了)
 * 1)前半部分在构建堆的时候，每个非叶子结点都需要与其孩子进行比较互换，最多进行两次比较和互换，所以时间复杂度是O(n)
 * 2)后半部分在正式排序的时候，第i次取堆顶元素并重建大根堆需要O(log n),总共需要取n-1次堆记录，所以时间复杂度是 O(nlogn)
 * 所以总的时间复杂度为O(nlogn)
 */
public class HeapSort {
    @Test
    public void test() {
//        int[] nums = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        int[] nums = {5, 2, 7, 4, 1, 3, 8, 9};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    // 堆排序
    void heapSort(int[] nums) {
        // 这里的len是数组长度而不是下标
        int len = nums.length;
        // 注: 以0开始编号的完全二叉树,最后一个非叶子结点的编号为: len / 2 - 1
        // 1.先建堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            // 迭代调整每一个子树为堆
            adjustHeap(nums, i, len);
        }
        // 2.交换堆顶元素并重新调整堆
        for (int i = len - 1; i >= 0; i--) {
            // 交换堆顶元素
            swap(0, i, nums);
            // 交换完结点之后，根结点的左右子树还是满足堆结构，所以只需要调用一次adjustHeap
            // 即可重新调整堆，而不需要多次循环
            adjustHeap(nums, 0, i);
        }
    }

    /**
     * 调整堆的操作(大顶堆)
     * @param nums
     * @param i
     * @param len 不包括len,这里的len是边界 **
     */
    void adjustHeap(int[] nums, int i, int len) {
        int temp = nums[i];
        // 从0开始编号,左孩子序号为 2i+1
        for (int j = 2 * i + 1; j < len; j = j * 2 + 1) {
            // 这里应该是 j < len, 而不是 j <= len,不然下面的 nums[j+1]就可能会越界

            // len 是数组长度而不是最后一个元素的下标
            if (j + 1 < len && nums[j] < nums[j + 1]) {
                // j 指向左右结点的较大值
                j++;
            }
            if (temp > nums[j]) break;
            nums[i] = nums[j];
            i = j;
        }
        nums[i] = temp;
    }

    void swap(int i, int j, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
